A hash table is a data structure used fast and efficient lookup of information using a key derived from an input. The hash table can be implemented in an associative array, which is a structure that can map the keys to the information. The hash table uses a hash function to compute an index into an array of buckets containing the corresponding information (the buckets can also be referred to as slots). Upon input of the key, the hash function is executed and the resulting index used to obtain the correct value from the data structure.
The hash table is more efficient than using the entire key, which may be quite large, because a lookup using a smaller index is faster even with the overhead of the hash function execution. The hash function should generate an index to map each possible input key to a unique bucket, but the hash function is not always able to achievable this one to one relationship in practice. Instead, most hash table designs assume that hash collisions can occur. A hash collision is a case where two input keys generate the same key index when the hash function is applied. Thus, both keys are assigned by the hash function to the same bucket, which requires a collision resolution process to correct or a carefully controlled hash table.
In a well-dimensioned hash table, the resources required for each lookup is independent of the number of different elements stored in the hash table. A hash table designs can also support insertions and deletions of buckets. In many scenarios, hash tables are the most efficient table lookup structure. For this reason, they are widely used in many kinds of computer programs for fast data lookup.
Hash table collision resolution is often needed when hashing a random subset of a large set of possible keys. Therefore, most hash table implementations have some collision resolution strategy to handle such events. All these methods require that the keys (or pointers to them) be stored in the table, together with the associated values.